Konkurs programistyczny

Limit pamięci: 64 MB

Bajtazar przygotowuje się do udziału w finale indywidualnego konkursu programistycznego. W ramach przygotowań bardzo wnikliwie przeczytał regulamin konkursu, jak również zasady organizacji zawodów, i dowiedział się, że w finale będzie do rozwiązania dokładnie zadań, a każde zadanie będzie należało do jednej spośród dziedzin. Może się zdarzyć więcej niż jedno zadanie z danej dziedziny. Bajtazar zna dobrze wszystkich uczestników finału i dla każdego zawodnika wie, jakie są jego kompetencje w poszczególnych dziedzinach. Kompetencja w dziedzinie wyraża się zawsze dodatnią liczbą całkowitą; wyższa liczba oznacza wyższe umiejętności.

Każde zadanie w konkursie będzie miało pewną trudność, określoną dodatnią liczbą całkowitą. Bajtazar zakłada, że dane zadanie rozwiążą tylko ci zawodnicy, których kompetencja jest nie mniejsza niż trudność danego zadania. Za zadanie, które zrobi, zawodnik otrzyma liczbę punktów równą różnicy swojej kompetencji w danej dziedzinie i trudności zadania. Ostateczny ranking jest ustalany przede wszystkim według liczby rozwiązanych zadań (tj. zawodnik, który zrobił więcej zadań, jest zawsze wyżej w rankingu niż ten, który zrobił mniej), a wśród zawodników o tej samej liczbie zadań - według punktacji (im więcej punktów, tym zawodnik jest wyżej sklasyfikowany).

Bajtazar, zamiast porządnie trenować do konkursu, zaczął zastanawiać się, czy istnieje taki dobór zadań, przy którym wygra. Nie umie jednak tego stwierdzić (a poza tym chciałby może jednak jeszcze trochę potrenować), więc poprosił Cię o pomoc. Możesz założyć, że ewentualne remisy są rozstrzygane na niekorzyść Bajtazara.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita () oznaczająca liczbę zestawów testowych. W kolejnych wierszach znajdują się opisy poszczególnych zestawów.

W pierwszym wierszu opisu każdego zestawu znajdują się trzy dodatnie liczby całkowite , i (, ), pooddzielane pojedynczymi odstępami i oznaczające kolejno liczby zadań, zawodników oraz dziedzin, do których należą zadania. Dalej następuje wierszy opisujących poszczególnych zawodników. W -tym z nich znajduje się liczb całkowitych z przedziału , pooddzielanych pojedynczymi odstępami, oznaczających kompetencje -tego zawodnika w kolejnych dziedzinach. Pierwszy spośród tych wierszy opisuje umiejętności Bajtazara.

Wyjście

Na standardowe wyjście należy wypisać dokładnie wierszy, po jednym dla każdego zestawu testowego. Odpowiedzią dla każdego zestawu jest jedno słowo TAK lub NIE, oznaczające, czy Bajtazar ma szansę zwyciężyć w konkursie.

Przykład

Dla danych wejściowych:

2
3 6 5
70 100 100 70 100
205 180 70 200 150
180 200 30 25 45
75 45 80 180 180
120 10 120 90 10
15 110 135 150 210
2 2 2
12 12
20 20

poprawną odpowiedzią jest:

TAK
NIE

Wyjaśnienie do przykładu: Dla pierwszego testu przykładowym zestawem zadań, przy którym Bajtazar zwycięży w finale, jest: zadanie z pierwszej kategorii o trudności 5, zadanie z drugiej kategorii o trudności 20 oraz zadanie z trzeciej kategorii o trudności 75. Wtedy końcowa tabela wygląda następująco:

1. Bajtazar (zawodnik 1): 3 zadania, 170 punktów
2. Zawodnik 6: 3 zadania, 160 punktów
3. Zawodnik 4: 3 zadania, 100 punktów
4. Zawodnik 2: 2 zadania, 360 punktów
5. Zawodnik 3: 2 zadania, 355 punktów
6. Zawodnik 5: 2 zadania, 160 punktów

Autor zadania: Jakub Onufry Wojtaszczyk.